package question.solution647;

import question.SolutionTemplate;

public class Solution647 implements SolutionTemplate {


    /**
     * 使用Manacher算法
     * @param s
     * @return
     */
    public int countSubstrings(String s) {

        /**
         * 第一步，填充分隔字符#
         */
        char[] completeString = completeString(s,'#');
        /**
         * 第二步，开始计算
         */
        int[] plalindromeRadius = new int[completeString.length];
        int maxPlalindromeEndIndex = 0;
        int maxPlalindromeEndCenterIndex = 0;
        for(int nowCenterIndex=0;nowCenterIndex<completeString.length && maxPlalindromeEndIndex<completeString.length;nowCenterIndex++){
            if(nowCenterIndex<maxPlalindromeEndIndex){
                plalindromeRadius[nowCenterIndex] = Math.max(plalindromeRadius[2*maxPlalindromeEndCenterIndex-nowCenterIndex],maxPlalindromeEndIndex-nowCenterIndex);
            }else{
                plalindromeRadius[nowCenterIndex] = 1;
            }

        }

        return 0;
    }

    @Override
    public void test() {

    }

    private char[] completeString(String source, char spliter){
        StringBuffer stringBuffer = new StringBuffer();
        for(int i=0;i<source.length();i++){
            stringBuffer.append(spliter).append(source.charAt(i));
        }
        stringBuffer.append(spliter);
        return stringBuffer.toString().toCharArray();
    }
}
